package DoExercise.HSP_ZCY.A009_图结构.A001_并查集;

import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * 从随机的某点开始，求图中的最短联通路径
 * <p>
 * 思路
 * 1 随机从一个点出发，找该点的最小权重边
 * 2 判断最小权重边涉及的点是否已经存在集合中（是否联通）
 * 3 如果存在（已经连通），就跳过该边
 * 4 如果不在，就以该点为新点，在做1-4的处理
 * 5 直到所有的遍历都处理完成
 * <p>
 * 两者区别
 * 克鲁斯卡尔算法直接从最小的边开始选择，生成最小树，直接来，普里姆是从某个节点开始，每次选择当前节点所能选到的最小边，生成最小树，间接来。
 */
public class Code05_普里姆算法_P算法
{
    public static class EdgeComparator implements Comparator<Edge>
    {
        @Override
        public int compare(Edge o1, Edge o2)
        {
            return o1.weight - o2.weight;
        }
    }
    
    public static Set<Edge> primMST(Graph graph)
    {
        // 解锁的边进入小根堆
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
        HashSet<Node> nodeSet = new HashSet<>();//点集
        HashSet<Edge> edgeSet = new HashSet<>();//边集
        
        Set<Edge> result = new HashSet<>(); // 依次挑选的的边在result里
        for (Node node : graph.nodes.values())//for循环的意义就是防止森林的存在，森林就是图中有很多图，彼此间没有联通
        {
            //node 是开始点
            if (!nodeSet.contains(node))
            {
                nodeSet.add(node);
                for (Edge edge : node.edges)
                {
                    if (!edgeSet.contains(edge))
                    {
                        priorityQueue.add(edge);// 由一个点，解锁所有相连的边
                        edgeSet.add(edge);//防止一条边多次进入
                    }
                }
                //从边的小根堆中挑出一个最小的边出来
                while (!priorityQueue.isEmpty())
                {
                    Edge edge = priorityQueue.poll(); // 弹出解锁的边中，最小的边
                    Node toNode = edge.to; //判断to是否在点的集合里
                    if (!nodeSet.contains(toNode))//不在就加入
                    {
                        nodeSet.add(toNode);
                        result.add(edge);
                        for (Edge nextEdge : toNode.edges)//to点在解锁所有的边，重复上面找最小权重边的过程
                        {
                            if (!edgeSet.contains(nextEdge))//防止一条边多次进入
                            {
                                priorityQueue.add(nextEdge);// 由一个点，解锁所有相连的边
                                edgeSet.add(nextEdge);//防止一条边多次进入
                            }
                        }
                    }
                }
            }
            break;//不考虑for循环，就是随机一个点开始，做一次就可以生成最小生成树
        }
        return result;
    }
    
    // 请保证graph是连通图
    // graph[i][j]表示点i到点j的距离，如果是系统最大值代表无路
    // 返回值是最小连通图的路径之和
    public static int prim(int[][] graph)
    {
        int size = graph.length;
        int[] distances = new int[size];
        boolean[] visit = new boolean[size];
        visit[0] = true;
        for (int i = 0; i < size; i++)
        {
            distances[i] = graph[0][i];
        }
        int sum = 0;
        for (int i = 1; i < size; i++)
        {
            int minPath = Integer.MAX_VALUE;
            int minIndex = -1;
            for (int j = 0; j < size; j++)
            {
                if (!visit[j] && distances[j] < minPath)
                {
                    minPath = distances[j];
                    minIndex = j;
                }
            }
            if (minIndex == -1)
            {
                return sum;
            }
            visit[minIndex] = true;
            sum += minPath;
            for (int j = 0; j < size; j++)
            {
                if (!visit[j] && distances[j] > graph[minIndex][j])
                {
                    distances[j] = graph[minIndex][j];
                }
            }
        }
        return sum;
    }
}
